package com.mc.sort;

import java.util.Arrays;

/**
 * @Description: 堆排序
 * @Author: MoChen
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arrs = {1, 2, 5, 3, 6, 7, 4};
        heapSort(arrs);
        System.out.println(Arrays.toString(arrs));
    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] arrs){
        // 1. 构建大顶堆
        for(int i = arrs.length / 2 - 1; i >= 0; i--){
            adjustHeap(arrs, i, arrs.length);
        }
        // 2. 调整堆结构 + 交换堆顶元素与末尾元素
        for(int j = arrs.length - 1; j > 0; j--){
            swap(arrs, 0, j);
            adjustHeap(arrs, 0, j);
        }
    }

    /**
     * 调整大顶堆
     */
    public static void adjustHeap(int[] arrs, int i, int length){
        int temp = arrs[i];
        for(int k = i * 2 + 1; k < length; k = k * 2 + 1){
            if(k + 1 < length && arrs[k] < arrs[k + 1]){
                k++;
            }
            if(arrs[k] > temp){
                arrs[i] = arrs[k];
                i = k;
            }else{
                break;
            }
        }
        arrs[i] = temp;
    }

    /**
     * 交换元素
     */
    public static void swap(int[] arrs, int a, int b){
        int temp = arrs[a];
        arrs[a] = arrs[b];
        arrs[b] = temp;
    }
}
